package zuoshen_video2.stack;

import java.util.*;

import org.junit.Test;

//在重复数组中找到最近的比他大的元素
public class RepeatNearestBigger {
    
    public int[][] nearBigger(int[] nums) {
        int len = nums.length;
        int[][] res = new int[len][2];
        Stack<LinkedList<Integer>> stack = new Stack<>();

        LinkedList<Integer> list;
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && nums[stack.peek().peekLast()] < nums[i]) {
                list = stack.pop();
                int left = stack.isEmpty() ? -1 : stack.peek().peekLast();
                for (int e: list) {
                    res[e][0] = left;
                    res[e][1] = i;
                }
            }
            if (stack.isEmpty() || nums[stack.peek().peekLast()] > nums[i]) {
                list = new LinkedList<>();
                list.addLast(i);
                stack.push(list);
            } else {
                stack.peek().addLast(i);
            }
        }
        int left, right, cur = -1;
        if (!stack.isEmpty()) {
            right = -1;
            while (!stack.isEmpty()) {
                list = stack.pop();
                left = stack.isEmpty() ? -1 : stack.peek().peekLast();
                for (int c: list) {
                    res[c][0] = left;
                    res[c][1] = right;
                    cur = c;
                }
                right = cur;
            }
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = {5,4,3,4,2,3,5,6};
        int[][] res = nearBigger(nums);
        System.out.println(Arrays.deepToString(res));
    }
}
